"""
桶排序：数据分布范围不大，建一个桶将数据分区存储，桶内使用插入排序
计数排序：数据分布范围不大，通过一个覆盖分布范围的大桶记录每个元素出现的次数
"""
import sys

print(sys.getsizeof([0]))
print(sys.getsizeof([0] * 100))
print(sys.getsizeof([0] * 1000))


def count_sort(nums):
    """计数排序
    :param nums: 待排序的列表
    :returns: 排好序的列表
    """
    bucket = [0] * 100
    for num in nums:
        bucket[num] += 1
    nums = []
    for index, value in enumerate(bucket):
        if value > 1:
            nums += [index] * value
        elif value > 0:
            nums.append(index)
    return nums


nums = [35, 99, 12, 78, 55, 69, 40, 21, 78, 12]
print(count_sort(nums))
print(nums)

# 列表中有1000000个元素，取值范围是[1000, 10000)，
# 设计一个函数找出列表中的重复元素并返回
def find_dups(items):
    bucket = [0] * 9000
    for item in items:
        bucket[item - 1000] += 1
    return [1000 + index 
            for index, value in enumerate(bucket) if value > 1]
